#include<iostream>
#include<cstring>
#include<arm_neon.h>
#include<sys/time.h>
using namespace std;
int N = 10000;
int g[N][N], dist[N], st[N];
void dijkstra(int n) {
	dist[1] = 0;
	for (int i = 0; i < n - 1; ++i) {
		int t = -1;
		for (int j = 1; j <= n; ++j)
			if (!st[j] && (t == -1 || dist[t] > dist[j]))
				t = j;
		st[t] = 1;
		int j = 1;
		for (j=1; j + 4 <= n; j += 4) {
			int32x4_t t1 = vld1q_s32(&dist[j]);
			int32x4_t t2 = vld1q_s32(&g[t][j]);
			int32x4_t t3 = vmovq_n_s32(dist[t]);
			t2 = vaddq_s32(t2, t3);
			t1 = vminq_s32(t1, t2);
			vst1q_s32(&dist[j], t1);
		}
		for (int k=j; k <= n; ++k)
			dist[k] = min(dist[k], dist[t] + g[t][k]);
	}
}
int main(int argc,char** args) {
	int n, m;
	cin >> n >> m;
	for (int i = 1; i <= n; ++i)g[i][i] = 0;
	memset(dist, 0x3f, sizeof dist);
	memset(g, 0x3f, sizeof g);
	for (int i = 0; i < m; ++i) {
		int a,b,c;
		scanf("%d%d%d", &a, &b, &c);
		if (c > g[a][b] || a == b)continue;
		g[a][b]= c;
	}
	

    struct timeval t1,t2;
    double time=0.0;
	gettimeofday(&t1,NULL);
	////
	dijkstra(n);
	////
	gettimeofday(&t2,NULL);
	time=(double)(t2.tv_sec-t1.tv_sec)*1000.0 + (double)(t2.tv_usec-t1.tv_usec)/1000.0;
	cout<< time;
}